from typing import List


# 排序二叉树非平衡树
# class KthLargest(object):
#     class TreeNode:
#         def __init__(self, val):
#             self.val = val;
#             self.right = None;
#             self.left = None;
#             self.n = 1
#             self.cnt = 1
#
#     def __init__(self, k, nums):
#         """
#         :type k: int
#         :type nums: List[int]
#         """
#         self._root = None
#         for x in nums:
#             self._work(self._root, x)
#         self._k = k
#
#     def _work(self, p, k):
#         if not p:
#             self._root = self.TreeNode(k)
#             return
#         elif k < p.val:
#             if p.left:
#                 self._work(p.left, k)
#             else:
#                 p.left = self.TreeNode(k)
#         elif k > p.val:
#             if p.right:
#                 self._work(p.right, k)
#             else:
#                 p.right = self.TreeNode(k)
#         else:
#             p.n += 1
#         p.cnt += 1
#
#     def _find(self, p, k):
#         r = p.right.cnt if p.right else 0
#         if k > r and k <= r + p.n:
#             return p.val
#         elif k <= r:
#             return self._find(p.right, k)
#         else:
#             return self._find(p.left, k - r - p.n)
#
#     def pop(self):
#         p, q = self._root, None
#         while p and p.left:
#             p, q = p.left, p
#         if p and p.n>1:
#             p.n -= 1
#         elif not q:
#             if p and p.right:
#                 self._root = p.right
#         elif p.right:
#             q.left = p.right
#         else:
#             q.left = None
#
#     def add(self, val):
#         """
#         :type val: int
#         :rtype: int
#         """
#         self._work(self._root, val)
#         if self._root.cnt>self._k:
#             self.pop()
#         return self._find(self._root, self._k)


# 小根堆
class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.k = k
        nums.sort(key=lambda x: -x)
        # nums.reverse()
        self.data = nums[:self.k]
        self.data.reverse()
        self.l = len(self.data)

    def _down(self, i=0):
        # print(f' down:{self.data}|{self.l}|{self.k},{i}')
        k = i * 2 + 1
        while i < self.l and k < self.l:
            k = i * 2 + 1
            if k + 1 < self.l and self.data[k + 1] < self.data[k]:
                k += 1
            if self.data[i] > self.data[k]:
                self.data[i], self.data[k] = self.data[k], self.data[i]
            i = k
            k = i * 2 + 1

    def add(self, val: int) -> int:
        if self.l < self.k:
            self.data.append(val)
            self.l += 1
        elif self.data[0] < val:
            self.data[0] = val
        else:
            return self.data[0]
        self._down()
        return self.data[0]

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)


# kth = KthLargest()

questions = [
    (3, [4, 5, 8, 2], [3, 5, 10, 9, 4]),
    (1, [], [-3, -2, -4, 0, 4]),
    (3, [5, -1], [2, 1, -1, 3, 4]),
]

for qi, q in enumerate(questions, 1):
    k, nums, qs = q
    print(f'#{qi}:', k, nums)
    kth = KthLargest(k, nums)
    print(' ', end='')
    for j in qs:
        print(f'{j}:{kth.add(j)}', end=',')
    print('')

